8、完美队列的数目
题目 完美队列的数目
思路分析
双指针加快速幂
好离谱的地方就是 我双指针对撞指针的板子居然只能过60% 不如这个true时i++ false时j--快 没搞懂为什么 按道理应该是一样的吧
我真的很不理解 明明没走回头路 j是一直递减的 为什么效率会低一倍
chatgpt也讲不出哪里有问题
第一段代码中，通过固定l并向左移动r来减小和的策略本质上是利用了数组的有序性。r的移动是单向的，它不会重置或回头，这意味着它确实是高效的。每次当l向右移动时，因为数组是有序的，l的增大只会增加找到满足a[l] + a[r] <= k条件的难度，因此r可能需要进一步向左移动。
第二段代码中，策略基于a[l] + a[r]与k的比较来决定是增加l还是减少r。这种方法直接寻找满足条件的边界，同时避免了不必要的计算。当a[l] + a[r] <= k时，这意味着所有当前l到r之间的组合都是有效的，因此可以直接计算这些组合而不再单独检查。
性能差异的再分析：
在再次审视你的解释后，如果两段代码之间存在性能差异，这不应该是由于r回头移动导致的，因为在你的代码中r是单向移动的。
可能的性能差异原因包括：
计算次数的差异：第二种方法中，当找到满足条件的组合时，会立即计算从l到r的所有可能组合数量，然后l++或r--。这种方法可能在某些情况下减少了计算量，因为它立即利用当前的边界计算了所有有效的组合，而不是单独考虑每个l的位置。
具体实现细节：实际性能差异可能还受到编译器优化、具体实现的细节以及运行时环境的影响。例如，循环中的条件检查、函数调用的开销等，都可能对性能产生影响。
代码逻辑的微小差异：尽管两种策略在高层次上类似（都是利用双指针和有序数组的特性），但具体的实现逻辑（如何更新l和r、何时进行计算等）可能导致执行效率上的差异。
代码实现
9/15
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long LL;
const int N=1e5+10,mod=1e9+7;
int a[N];
LL qmi(LL a,int k){
LL res=1%mod;
while(k){
if(k&1)
res=res*a%mod;
k>>=1;
a=a*a%mod;
}
return res;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,k;cin>>n>>k;
for(int i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);
LL ans=0;
for(int l=0,r=n-1;l<=r;l++){
while(r>=l && a[l]+a[r]>k)
r--;
if(a[l]+a[r]<=k){
ans=(ans+qmi(2,r-l))%mod;
}
}
cout<<ans;
return 0;
}
ac
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long LL;
const int N=1e5+10,mod=1e9+7;
int a[N];
LL qmi(LL a,int k){
LL res=1%mod;
while(k){
if(k&1)
res=res*a%mod;
k>>=1;
a=a*a%mod;
}
return res;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,k;cin>>n>>k;
for(int i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);
LL ans=0;
for(int l=0,r=n-1;l<=r;){
if(a[l]+a[r]<=k){
ans=(ans+qmi(2,r-l))%mod;
l++;
}
else
r--;
}
cout<<ans;
return 0;
}
同类题型
视频讲解
⬅️ 7、基德的密码锁 🏠 00-刷题理模型 ➡️ 9、GCD王国和LCM王国
💬 评论